package com.tianlh.service.exam;

/**
 * @author 黑子
 * @Date 2018/2/10 10:25
 */
public class QuickSort {
    /*
    *@desc 采用分而治之递归调用的思想，每次将数组元素的第一个值作为基准值base;
    * 1）从右边开始找到第一个比基准值小的元素(每找一次right--),并将这个元素复值给基准值当前的下标元素arr[left];
    * 2）从左边开始找到第一个比基准值大的元素(每找一次left++)，将该元素赋值给下标为right的元素arr[right];
    * 3）将base赋值给下标为arr为left的元素[left];
    * 4）递归以上操作，终止条件是：left<right;
     */

    private static int division(int[] arr, int left, int right){
        int base = arr[left];
        while (left < right){
            while (left < right && arr[right] > base){
                --right;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] < base){
                ++left;
            }
            arr[right] = arr[left];
        }
        arr[left] = base;
        return left;
    }

    private static void sort(int[] arr, int left, int right){
        int i;
        if(left < right){
            i = division(arr, left, right);
            sort(arr, left, i-1);
            sort(arr, i+1, right);
        }
    }

    public static void main(String[] args) {
/*        int[] arr = new int[]{2,4,3,5,1,6,9};
        sort(arr, 0, arr.length - 1);
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }*/

        TestFinalInstance instance = TestFinalInstance.getInstance();
        instance.setName("黑子");
        System.out.println(instance);
        TestFinalInstance instance1 = TestFinalInstance.getInstance();
        instance.setName("大约");
        System.out.println(instance);
        System.out.println(instance1);
    }
}
